/*
 * @lc app=leetcode.cn id=300 lang=javascript
 *
 * [300] 最长上升子序列
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @return {number}
 */

// dp
var lengthOfLIS1 = function(nums) {
    let dp = new Array(nums.length).fill(0)
    dp[0] = 1
    let max = 1
    for (let i = 1; i < nums.length; i++) {
        let j = i
        while (j > 0) {
            if (nums[--j] < nums[i])
                dp[i] = Math.max(dp[j], dp[i])
        }
        dp[i] += 1
        max = Math.max(dp[i], max)
    }
    return max
};

// 贪心
// 上升序列最后加上的那个数尽可能的小
// 用一个数组d[i]表示长度为i的最长上升子序列的末尾元素的最小值
var lengthOfLIS2 = function(nums) {
    if (nums.length < 1) return 0
    let d = [nums[0]], len = 1
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] > d[len-1]) {
            d.push(nums[i])
            len++
        } else { // 二分查找
            let p = -1, l = 0, r = len - 1
            while (l <= r) {
                let mid = (l + r) >> 1
                if (d[mid] < nums[i]) {
                    p = mid
                    l = mid + 1
                } else {
                    r = mid - 1
                }
            }
            d[p+1] = nums[i]
        }
    }
    return len
};

// @lc code=end

lengthOfLIS2([10,9,2,5,3,7,101,18])